/**
 *   @file AvlTree.h
 */
#ifndef _AVLTREE_H_
#define _AVLTREE_H_

#include "BinTree.h"
#include "AvlTreeNode.h"

namespace cppflib
{

namespace collections
{

namespace tree
{

/**
 *  An implementation of the balanced AVL tree
 */
class _DLLAPI AvlTree : public BinTree
{
public:
    AvlTree(void);
    virtual ~AvlTree(void);

    /*
     *  Though it accepts 'TreeNode', it must be an AvlTreeNode derived object
     */
    virtual bool Insert(TreeNode *pNode);
    virtual bool Delete(const TreeNode &node);

private:
    //! rotation type
    typedef enum {
       RT_NONE = 0,   ///< no rotation
       RT_LL,         ///< left-left 
       RT_RR,         ///< right-right
       RT_RL,         ///< right-left
       RT_LR          ///< left-right
    } rotatetype_t;

    AvlTreeNode * __LeftRight_Rotate(AvlTreeNode *pUnbalancedNode);
    AvlTreeNode * __RightLeft_Rotate(AvlTreeNode *pUnbalancedNode);
    void __RotateInsert(rotatetype_t rType, AvlTreeNode *pUnbalancedNode);
    rotatetype_t __UpdateBalanceInsert(AvlTreeNode *pNode, AvlTreeNode **pUnbalancedNode);
    AvlTreeNode * __RotateDelete(rotatetype_t rType, AvlTreeNode *pUnbalancedNode);
    rotatetype_t __UpdateBalanceDelete(AvlTreeNode *pPrevParent, bool isLeftChild, AvlTreeNode **pUnbalancedNode);

};

}  // end of namespace tree

}  // end of namespace collections

}  // end of namespace cppflib


#endif
